package com.zklh.leetcode.other.problem63;
/**
 * @descrpiton 不同路径2算法实现
 * @author 坐看落花
 * @version 1.0
 * @date 2019/10/12
 */
public class Solution {


    /**
     * 使用动态规划+ 递归实现的不同路径算法
     * 此外还有一种不使用递归的动态规划算法
     * 这里将obstacleGrid存储路径数
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        /* 这里修改障碍规则, -1表示障碍, -2表示为空 */
        // 这里需要使用obstacleGrid存储x,y节点到0,0的路径数, 如果小于0表示还未计算
        // 如果大于等于0,表示已经计算过路径了, 直接取即可
        int x = obstacleGrid.length-1;
        int y = obstacleGrid[0].length-1;

        // 这里排除下 只有一个节点情况
        if(x == 0 && y == 0){
            return obstacleGrid[x][y] == 1 ? 0 : 1;
        }

        // 这里排除下根为障碍的情况
        if(obstacleGrid[0][0] == 1 || obstacleGrid[x][y] == 1){
            return 0;
        }

        for (int i = 0; i <= x; i++) {
            for (int j = 0; j <= y; j++) {
                if(obstacleGrid[i][j] == 1){
                    obstacleGrid[i][j] = -1;
                }else{
                    obstacleGrid[i][j] = -2;
                }
            }
        }
        /* 这里更新0,0相邻的两个节点距离0的路径数 */
        if(x >= 1){
            if (obstacleGrid[1][0] == -1) {
                obstacleGrid[1][0] = 0;
            }else{
                obstacleGrid[1][0] = 1;
            }
        }
        if(y >= 1){
            if (obstacleGrid[0][1] == -1) {
                obstacleGrid[0][1] = 0;
            }else{
                obstacleGrid[0][1] = 1;
            }
        }
        return uniquePathsWithObstacles(obstacleGrid,x,y);
    }

    /**
     * 得到x,y距离0,0的路径数
     * 在使用之前obstacleGrid需要进行转化, 和初始化0,1, 0,1两个节点的路径数
     * @param obstacleGrid
     * @param x
     * @param y
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid, int x, int y){

        // 终止条件,
        if((x == 0 && y == 0) || (x == 1 && y == 0)){
            return obstacleGrid[x][y];
        }

        // 这里如果当前节点是障碍直接返回0,并更新obstacleGrid x,y 到0,0路径数为0
        if(obstacleGrid[x][y] == -1 || obstacleGrid[x][y] == 0){
            obstacleGrid[x][y] = 0;
            return 0;
        }

        // 这里定义左节点和上节点到0,0的路径数
        int leftNodePaths,upNodePaths;

        /* 获得左节点的路径数 */
        /* 如果左节点存储值小于0,表示左节点的到0,0的路径数还没计算过, 需要计算, */
        /* 并更新uniquePathsWithObstacles存储左节点到0,1的值 */

        // 如果是左边界, 左节点越界, 到0,0路径数直接为0
        if(x == 0){
            leftNodePaths = 0;
        }else{
            // 如果没有计算过
            if(obstacleGrid[x-1][y] < 0){
                leftNodePaths = uniquePathsWithObstacles(obstacleGrid,x-1,y);
                obstacleGrid[x-1][y] = leftNodePaths;
            }else{ // 如果值大于等于0,说明已经计算过直接取值即可,无需额外计算
                leftNodePaths = obstacleGrid[x-1][y];
            }
        }

        /* 获取上节点距离0,0的路径数, 计算逻辑左节点一样 */
        if(y == 0){
            upNodePaths = 0;
        }else{
            // 如果没有计算过
            if(obstacleGrid[x][y-1] < 0){
                upNodePaths = uniquePathsWithObstacles(obstacleGrid,x,y-1);
                obstacleGrid[x][y-1] = upNodePaths;
            }else{ // 如果值大于等于0,说明已经计算过直接取值即可,无需额外计算
                upNodePaths = obstacleGrid[x][y-1];
            }
        }

        return upNodePaths + leftNodePaths;
    }


    public static void main(String[] args){
        int[][] grid = {
                {0,0,0},
                {0,1,0},
                {0,0,0}
        };
        Solution solution = new Solution();
        System.out.println(solution.uniquePathsWithObstacles(grid));
    }

}

